package com.cqs.leetcode.unionfind;

import java.util.Random;

/**
 * @author lixiaowen
 * @create 2019-12-20
 */
public class FriendCircles547 {


    /**
     * 思路：
     * 1. 将相邻的人分到一个堆里面
     * 2. 最后求堆的个数
     */
    static class Solution {

        /**
         * 思路：
         * 1. 将相邻的人分到一个堆里面
         * 2. 最后求堆的个数
         */
        private int[] initGroups(int[][] friends) {
            int[] group = new int[friends.length];
            for (int i = 0; i < friends.length; i++) {
                group[i] = i;
            }
            return group;
        }

        public int findCircleNum(int[][] friends) {
            if (friends == null || friends.length == 0) return 0;
            //记录每个人所属的分组
            int[] groups = initGroups(friends);
            //union
            for (int i = 0; i < friends.length; i++) {
                for (int j = 0; j < friends[i].length; j++) {
                    //find  判断是否相连
                    if (friends[i][j] == 1 && groups[i] != groups[j]) {
                        //小root
                        int minGroupRoot = groups[i] < groups[j] ? groups[i] : groups[j];
                        //
                        int maxGroupRoot = groups[i] > groups[j] ? groups[i] : groups[j];
                        //压缩路径 ==》 find为O(1)
                        //maxGroupRoot合并至minGroupRoot
                        for (int k = maxGroupRoot; k < friends.length ; k++) {
                            if (groups[k] == maxGroupRoot){
                                groups[k] = minGroupRoot;
                            }
                        }
                    }
                }
            }
            //求分组的个数
            int groupNum = 0;
            for (int i = 0; i < groups.length; i++) {
                if (groups[i] == i) { groupNum++; }
            }
            return groupNum;
        }
    }


    public static void main(String[] args) {
        int N = 5;
        int[][] friends = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = i; j < N; j++) {
                if (i == j) {
                    friends[i][j] = 1;
                } else {
                    friends[j][i] = friends[i][j] = new Random().nextInt(N) == 1 ? 1 : 0;
                }
            }
        }

        int[][] friends2 = {
                {1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
                {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0},
                {0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0},
                {0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0},
                {1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0},
                {0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1},
                {0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}};


        Solution solution = new Solution();
        int circleNum = solution.findCircleNum(friends2);
        print(friends);
        System.out.println("result: " + circleNum);
    }

    private static void print(int[][] friends) {
        //int[][] friends = new int[N][N];
        int N = friends.length;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(friends[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("******************************************");
    }
}
